iT邦幫忙

2024 iThome 鐵人賽

DAY 12
0

題目

1684. Count the Number of Consistent Strings
難度: 超級簡單

題意

給定一字串allowed代表合法的字元,求字串陣列words中,只有合法字元出現的字串,有幾個。

方向

先用一個table紀錄allowed出現的字元,因為題目限定小寫的英文字母,所以開一個大小為26的bitset來存;如果字元範圍很大可以改用hash map做。
接著設定總數為零,一一檢查words字串之中的每個字元,若全部符合則總數加一,若有不符合的可以early return

實作

class Solution
{
public:
    int countConsistentStrings(string allowed, vector<string> &words)
    {
        bitset<26> allow(false);

        int res = 0;
        for (auto c : allowed)
            allow[c - 'a'] = true;

        for (auto word : words)
        {
            bool is_allowed = true;
            for (auto c : word)
            {
                is_allowed &= allow[c - 'a'];
                if(!is_allowed)
                    break;
            }
            if (is_allowed)
                res++;
        }
        return res;
    }
};

分析

words數量總長N
時間複雜度: O(N),每個字元最多檢查一次。
空間複雜度: O(1),table大小固定為26。

結果

Time Submitted Status Runtime Memory Language
09/12/2024 18:30 Accepted 43 ms 33.9 MB cpp
09/12/2024 18:29 Accepted 48 ms 33.9 MB cpp

雜談

9月鐵人賽開寫以來,題目都好簡單,要是面試也這麼輕鬆就好了(?

今天1點回家等冷氣師傅來裝新冷氣,結果5點才來,7點裝好...
終於有新冷氣吹了OAO
還好今天是easy題,吹著新冷氣寫個水題+1好愜意XD


上一篇
[9/11] 數幾個不一樣
下一篇
[9/13] 區間異或
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言